package bird.queue.array_queue;

import bird.queue.Queue;

import java.util.Arrays;

/**
 * @author sijunqiang
 * @data 2021/5/22 19:26
 * @description: 循环队列
 * 之所以会有循环队列,主要是数组队列在出队的时候 时间复杂度为O(n) 所以才会有循环队列
 */
public class LoopQueue<E> implements Queue<E> {

    // 底层真正存储元素的地方
    private E[] data;

    //代表队首位置的索引
    private int front;

    // 代表循环队列中,准备存放元素的索引的位置，这个位置和size指向的索引一致。
    private int tail;

    // size 代表队列中元素存储的个数,size指向的数组的索引位置是将要存放的元素的位置
    private int size;

    // construct function with param
    public LoopQueue(int capacity) {
        // 这里内存的容量+1 是代表着 要空出来一个 目的是 循环时候的使用,
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    // construct function not param
    public LoopQueue() {
        this(10);
    }

    public int getCapacity() {
        return data.length - 1;
    }

    @Override
    public void enqueue(E e) {
        //第一,先判断队列是否已满
        if (front == (tail + 1) % getCapacity()) {
            resize(2 * getCapacity());
        }
        // 第二,赋值 维护tail 变量和size长度
        data[tail] = e;
        // 因为是在循环队列中 如果仅仅是采用+1的方式维护tail的位置 会导致索引越界,所以采用模的方式维护tail的位置。
        tail = (tail + 1) % data.length;
        size++;
    }

    @Override
    public E dequeue() {
        // 第一, 先判断对列是否为空
        if (isEmpty()) {
            throw new IllegalArgumentException("loopqueue: is empty!");
        }
        // 第二，出队维护 front 的位置和size的长度 如果条件满足 需要进行缩容
        E ret = getFront();
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return ret;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("loopqueue: is empty!");
        }
        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public Boolean isEmpty() {
        return front == tail;
    }

    // 数组扩容： 扩容的思想-- 重新new出一个数组 将原始数组依次遍历 保存到新的数组中
    private void resize(int newCapacity) {
        // 扩容  front-- 代表队首 tail-代表 将要存放的元素的位置
        E[] newData = (E[]) new Object[newCapacity+1];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % data.length];// 这里采用取模的方式递进
        }
        data = newData;
        front = 0;
        tail = size;// size- 在数组中指向的位置 就是将要存放元素的位置 这个和tail是一致的
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
        res.append("loopQueue: front:");
        res.append('[');
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i + 1) % data.length != tail) {
                res.append(",");
            }
        }
        res.append(']');
        res.append(" tail");
        return res.toString();
    }
}
